package com.zx._12_算法.剑指offer._2022;

import com.zx.common.model.ListNode;

/**
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 *
 * https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
 */
public class 反转链表 {

    /**
     * 1. 递归处理
     *
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode r1 = head;
        ListNode r2 = head.next;
        ListNode res = null;

        if (r2.next != null) {
            res = reverseList1(r2);
        } else {
            res = r2;
        }

        r1.next = null;
        r2.next = r1;
        return res;
    }

    /**
     * 动态规划
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode next = head.next;
        cur.next = null;

        while (true) {
            ListNode nextNext = next.next;

            next.next = cur;

            if (nextNext == null) {
                break;
            }

            cur = next;
            next = nextNext;

        }

        return next;
    }

}
